The following relates to online non-stationary learning, workload usage or load prediction, and related arts.
Online learning entails predicting a parameter of interest as that parameter is changing, i.e. in approximately real-time. For example, in a distributed server or cloud computing environment, efficient distribution of processing work across the servers of the distributed server network or cloud enhances efficiency and maximizes the available computing capacity. Online workload or usage learning can be used to model, analyze and/or optimize this workload distribution. For example, in some illustrative environments, workload data are collected at 15 minute intervals, and it is desired for the online learning to generate a predictor that predicts the usage on a time scale of 15 minutes. This is merely an example, and the time frame for data collection is problem-specific.
Online learning is of especial value when the parameter of interest is non-stationary, that is, when its behavior on long time scales does not exhibit strong periodicity or repetitiveness or, more generally, the parameter being measured changes arbitrarily over time. In such non-stationary problems, the online learning should adapt on the time scale over which meaningful changes in the parameter value are expected. In the illustrative distributed computing example, workload distribution is expected to change arbitrarily over time due to various factors like change in the dominant application of target server (e.g., a web server reconfigured as a database server) or re-allocation of target server resulting in change of ownership (and hence usage) of the server, and so forth.
In a known approach for online prediction of a non-stationary parameter, an ensemble of regressors is used to deal with the non-stationarity aspect of the regression problem. See Kolter et al., “Dynamic weighted majority: An ensemble method for drifting concepts” J. Mach. Learn. Res., vol. 8, pp. 2755-90 (2007); Cosma Rohilla Shalizi et al., “Adapting to non-stationarity with growing expert ensembles” arXiv:1103.0949v (2011); Elwell et al., “Incremental learning of concept drift in nonstationary environments” Trans. Neur. Netw., vol. 22, no. 10, pp. 1517-31 (2011); Ditzler et al., “An incremental learning algorithm for non-stationary environments and class imbalance” in Proceedings of the 2010 20th International Conference on Pattern Recognition, ser. ICPR '10 (Washington, D.C., USA: IEEE Computer Society, 2010, pp. 2997-3000); Elwell et al., “Incremental learning of variable rate concept drift” in Proceedings of the 8th International Workshop on Multiple Classifier Systems, ser. MCS '09. Berlin, Heidelberg: Springer-Verlag, 2009, pp. 142-151. These algorithms typically create an ensemble of regressors trained over past data and then, after every t time steps (sometimes called an “episode”), evolve or refactor the ensemble composition by performing one or more ensemble actions such as adding a new regressor, fully or partially forgetting past knowledge by decaying one or more regressors, reassigning weights of regressors in accordance with predefined accuracy measure, reassigning weights of instances, or so forth in order to deal with non-stationarity of the environment.
These approaches are computationally inefficient for larger scale problems. By way of example, in the distributed computing workload prediction problem, the scale of workload data rapidly increases with the number of servers and with reduced time scale (i.e. short episodes and frequent updates). For accurate evolution of the ensemble, a number of computationally costly ensemble actions are taken after each episode, e.g. adding a new regressor and reassigning weights of all regressors or of all or most recent instances. For online non-stationary learning, this negatively impacts the execution speed of online prediction algorithm and is computationally expensive.